At times, data may be stored in in-memory data structures, such as a buffer, for fast access as opposed to accessing data directly from disk. In-memory data structures, however, may have limited capacity. Data compression may help maximize the capacity of an in-memory data structure by encoding the data using fewer bits than the original data representation. For example, an original data representation may occupy 500 bytes of an in-memory data structure and data compression techniques can encode the original data representation to create a compressed data representation that may occupy 450 bytes of the in-memory data structure.
Some traditional general purpose data compression/decompression solutions are dictionary-based systems that use a dictionary, for example, of strings of characters, to efficiently encode data. For example, the string “the” may frequently recur in a text document that is being encoded and a conventional compression solution may use an entry for “the” in a dictionary to encode the text document to create a compressed data representation. When decompressing the compressed data representation, conventional decompression solutions may use instructions in the compressed data representation to copy the string “the” from the dictionary to an output buffer to reconstruct the content of the text document.
The instructions in a compressed data representation describe the data that is to be copied to decompress the compressed data representation. Traditional solutions may interleave instructions with the data to be copied in the compressed data representation. For example, a compressed data representation may interleave instructions with data as follows: an instruction, data to be copied, an instruction, data to be copied, etc. Typical decompression solutions may not efficiently decode such a compressed data representation that interleaves one instruction with one set of data because repeatedly switching from reading instructions, to locating data to be copied, and to copying the data to an output buffer may increase processing time. Typical decompression solutions may also increase the processing time because they involve reading entire instructions before locating the data to be copied.
Some conventional compression/decompression solutions use a static dictionary that is made of integer values to compress/decompress integer data. Such solutions are limited to copying data from a dictionary and typically do not support compression/decompression of any data that does not reside in the dictionary.